package cn.test.ds.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author hanchao
 * @date 2018/3/21 10:46
 */
public class BSTree<T extends Comparable> {
    private TreeNode<T> root;


    public void remove(T data){
        TreeNode<T> node = searchNode(data);
        remove(node);
    }

    protected void remove(TreeNode node) {
        if(node == null){
            return;
        }
        if(node.left == null && node.right == null){
            TreeNode parentNode = node.parent;
            if(parentNode == null){
                root = null;
            }
            if (node == parentNode.left) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
        }else if (node.left == null && node.right != null) { // 该结点左孩子结点为空，右孩子结点非空
            TreeNode parentNode = node.parent;
            if(parentNode == null){
                root = node.right;
                return;
            }
            if (node == parentNode.left) {
                parentNode.left = node.right;
                node.right.parent = parentNode;
            } else {
                parentNode.right = node.right;
                node.right.parent = parentNode;
            }
        }else if(node.left != null && node.right == null){
            TreeNode parentNode = node.parent;
            if(parentNode == null){
                root = node.right;
                return;
            }
            if (node == parentNode.left) {
                parentNode.left = node.left;
                node.left.parent = parentNode;
            } else {
                parentNode.right = node.left;
                node.left.parent = parentNode;
            }
        } else{
            // 该结点左右孩子结点均非空，则删除该结点的后继结点，并用该后继结点取代该结点
            TreeNode successorNode = successor(node);
            remove(successorNode);
            node.data = successorNode.data;
        }
    }

    public boolean insert(T data) {
        if (data == null) {
            throw new NullPointerException("node cant be null");
        }
        TreeNode treeNode = new TreeNode(data);
        if (root == null) {
            root = treeNode;
            return false;
        }

        TreeNode current = root;
        while (current != null) {
            int compare = current.data.compareTo(data);
            if (compare == 0) {
                //节点已存在
                return false;
            } else if (compare > 0) {
                if (current.left == null) {
                    insertLeft(current, treeNode);
                    return true;
                } else {
                    current = current.left;
                }
            } else if (compare < 0) {
                if (current.right == null) {
                    insertRight(current, treeNode);
                    return true;
                } else {
                    current = current.right;
                }
            }
        }
        return false;
    }

    protected void insertRight(TreeNode parent, TreeNode node) {
        parent.right = node;
        node.parent = parent;
    }

    protected void insertLeft(TreeNode parent, TreeNode node) {
        parent.left = node;
        node.parent = parent;
    }

    protected TreeNode<T> searchNode(T data) {
        TreeNode<T> current = root;
        while (current != null) {
            int compare = current.data.compareTo(data);
            if (compare == 0) {
                //节点已存在
                return current;
            } else if (compare > 0) {
                current = current.left;
            } else if (compare < 0) {
                current = current.right;
            }
        }
        return null;
    }

    protected TreeNode predecessor(TreeNode<T> node) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (node == null) {
            throw new IllegalArgumentException("data is not exist");
        }
        if (node.left != null) {
            return maximum(node.left);
        } else {
            // 如果x没有左孩子。则x有以下两种可能：
            // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
            // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
            TreeNode parent = node.parent;
            while ((parent != null) && (node == parent.left)) {//如果依旧左结点继续向上，直到发现作为右节点为止,那么父节点就是前驱
                node = parent;
                parent = parent.parent;
            }
            return parent;
        }

    }

    protected TreeNode successor(TreeNode<T> node) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (node == null) {
            throw new IllegalArgumentException("data is not exist");
        }
        if (node.right != null) {
            return minimum(node.right);
        } else {
            // 如果x没有右孩子。则x有以下两种可能：
            // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
            // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
            TreeNode parent = node.parent;
            while ((parent != null) && (node == parent.right)) {//如果依旧左结点继续向上，直到发现作为左节点为止
                node = parent;
                parent = parent.parent;
            }
            return parent;
        }

    }

    protected TreeNode maximum(TreeNode<T> node) {
        if (node == null) {
            return null;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    protected TreeNode minimum(TreeNode<T> node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    //region ***iterators***
    protected void preOrder(TreeNode<T> node, List<T> datas) {
        if (node != null) {
            datas.add(node.data);
            preOrder(node.left, datas);
            preOrder(node.right, datas);
        }
    }

    public List<T> preOrder() {
        List<T> result = new ArrayList<T>();
        preOrder(root, result);
        return result;
    }

    protected void inOrder(TreeNode<T> node, List<T> datas) {
        if (node != null) {
            inOrder(node.left, datas);
            datas.add(node.data);
            inOrder(node.right, datas);
        }
    }

    public List<T> inOrder() {
        List<T> result = new ArrayList<T>();
        inOrder(root, result);
        return result;
    }

    protected void postOrder(TreeNode<T> node, List<T> datas) {

        if (node != null) {
            postOrder(node.left, datas);
            postOrder(node.right, datas);
            datas.add(node.data);
        }
    }

    public List<T> postOrder() {
        List<T> result = new ArrayList<T>();
        preOrder(root, result);
        return result;
    }
    //endregion


    protected static class TreeNode<T extends Comparable> {
        T data;
        TreeNode parent;
        TreeNode left;
        TreeNode right;

        public TreeNode(T data) {
            this.data = data;
        }

        public TreeNode(T data, TreeNode parent, TreeNode left, TreeNode right) {
            this.data = data;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

}
